package com.wangp.mywrite.coding;

/**
 * @author tooStrongerW
 * @version 1.0
 * @date 2021/3/30 21:16
 */
public class QuickSort extends Sort{

    public static void main(String[] args) {
        // 指定数组大小
        int capacity = 10_000;
        // 生成随机数组
        int[] arr = genRandomArr(capacity);
        // 排序
        quickSort(arr);
        // 断言数组顺序
        checkArrOrder(arr);
    }

    private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        // 递归退出条件
        if (left >= right) {
            return;
        }
        // 选取基准数
        int pivot = arr[left];
        int start = left;
        int end = right;
        // 开始比较
        while (start < end) {
            // 当 start 小于 end 并且后面的值大于或等于基准值的时候，后面指针向前移动
            while (start < end && arr[end] >= pivot) {
                end--;
            }
            // 填空
            if (start < end) {
                arr[start] = arr[end];
            }
            // 当 start 小于 end 并且前面面的值小于或等于基准值的时候，前面指针向后移动
            while (start < end && arr[start] <= pivot) {
                start++;
            }
            // 填空
            if (start < end) {
                arr[end] = arr[start];
            }
            // 比较完成，让基准数回到它该到的位置
            if (start >= end) {
                arr[start] = pivot;
            }
        }
        // 相同方式排序左子序列
        quickSort(arr, left, end - 1);
        // 相同方式排序右子序列
        quickSort(arr, end + 1, right);
    }
}
